package 牛客网在线编程题库;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 * 该二叉树层序遍历的结果是
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 */


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}


public class _求二次树的层序遍历 {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // 如果二叉树不存在，则直接返回
        if(root==null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        // 结果二维数组
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        // 存放每一层结点的数组
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 将根节点置入队列中，然后不断循环队列
        queue.add(root);
        // 当队列不为空的时候继续遍历
        while (queue.size() > 0) {
            // 获取当前队列的长度，这个长度相当于当前这一层的节点个数
            int size = queue.size();
            // 临时数组，用来存放遍历的数字
            ArrayList<Integer> temp = new ArrayList<>();
            // 将队列中的所有元素都取出，也即获取这一层的所有节点，放到临时数组中
            for (int i = 0 ; i < size ; i++) {
                // 从队列头弹出一个节点
                TreeNode t = queue.remove();
                // 将数值加入临时数组
                temp.add(t.val);
                // 如果其左右子树不为空，则放入队列中
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            // 将临时数组加入结果数组中
            list.add(temp);
        }
        return list;
    }
}
